{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Choosing `k` (or: How many clusters are in your data?)\n",
    "\n",
    "2015-07, Josh Montague \n",
    "\n",
    "*MIT License*\n",
    "\n",
    "\n",
    "# Intro\n",
    "\n",
    "There are often times when we'd like a representation of a dataset which reduces the dimensionality of the set of measurements. Having initially made $N$ measurements (observations) of $m$ features, the dimensionality of our problem space is $N \\times m$. We can reduce the dimensionality by making either $N$ or $m$ smaller.\n",
    "\n",
    "Techniques like principal component analysis and singular value decomposition are used to reduce the dimensionality by making $m$ smaller; these algorithms identify the most significant features to maintain sufficient variance in the data, and then ignore remaining features. That is, these techniques represent the original data by using all of the original measurements ($N$), but with a smaller number of features ($m$).\n",
    "\n",
    "Similarly, techniques like k-means clustering are meant to reduce the problem dimensionality by effectively making $N$ smaller; these algorithms collapse many \"nearby\" measurements (in the appropriate feature space) into a single representation using e.g. a single point (like a polygon centroid) to represent a bunch of other points. That is, these techniques represent the original data by using a smaller number of measurements and all of the original features; its a form of compression.\n",
    "\n",
    "And then, of course, you can also combine the two. But here, we're interested in the latter - reducing the data dimensionality by representing the data through clusters using the kmeans algorithm.\n",
    "\n",
    "\n",
    "\n",
    "# What is kmeans?\n",
    "\n",
    "K-means is a commonly used technique for compression. In machine learning, it's a common technique used for the unsupervised learning of structure within a set of observations. For details on the implementation of the kmeans algorithm, see both the [intro to kmeans in this repository](https://github.com/DrSkippy/Data-Science-45min-Intros/tree/master/k-means-101) and also [the documentation for the ``scikit-learn`` implementation](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html).\n",
    "\n",
    "\n",
    "## And what are we doing with it?\n",
    "\n",
    "In general, the parameter space in which we're trying to cluster our data can be arbitrarily large. In text analysis, a tfidf matrix on short documents can easily be 10,000-dimensional. Here, for the sake of simplicity (and plotting), we'll just use two orthogonal spatial dimensions.\n",
    "\n",
    "Let's get started by setting up and making some data in clusters (that is, we know the ground truth about cluster membership). Then, we'll look at it to get a sense for how these groupings are related to one another."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from scipy.spatial import distance\n",
    "import seaborn as sns\n",
    "\n",
    "from sklearn.datasets import make_blobs\n",
    "from sklearn.cluster import KMeans\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# generate some data\n",
    "clusters = 3\n",
    "samples = 100\n",
    "\n",
    "X, y = make_blobs(n_samples=samples, \n",
    "                  centers=clusters, \n",
    "                  n_features=2, \n",
    "                  cluster_std=1.0, \n",
    "                  # fix random_state if you believe in determinism\n",
    "                  random_state=42\n",
    "                 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set the plot style\n",
    "sns.set(style='darkgrid', palette='deep')\n",
    "\n",
    "# 1x3 subplots\n",
    "f, (ax1, ax2, ax3) = plt.subplots(1,3, sharey=True, sharex=True, figsize=(14,4))\n",
    "\n",
    "# plot all the data (left)\n",
    "ax1.plot(X[:,0], X[:,1], 'ok', alpha=0.5, label='all data')\n",
    "ax1.set_title('raw data')\n",
    "\n",
    "# show the clusters labeled as generated (middle)\n",
    "for i in range(clusters):\n",
    "    ax2.plot(X[y==i,0], X[y==i,1], 'o', alpha=0.5, label='cluster {}'.format(i))\n",
    "ax2.set_title('labeled clusters (ground truth)')\n",
    "ax2.legend(loc='best')\n",
    "\n",
    "# fit a default-settings KMeans model -- for now, assume we know k\n",
    "km = KMeans(n_clusters=clusters, n_jobs=-1).fit(X)\n",
    "# grab the model attributes once fit - we'll use these\n",
    "labels = km.labels_\n",
    "centers = km.cluster_centers_\n",
    "\n",
    "# show the clusters as fit by the KMeans model (right)\n",
    "for i in range(clusters):\n",
    "    ax3.plot(X[labels==i,0], X[labels==i,1], 'o', alpha=0.5, label='cluster {}'.format(i))\n",
    "# overlay the centroid points\n",
    "ax3.plot(centers[:,0], centers[:,1], \n",
    "         '^',\n",
    "         markerfacecolor='k', \n",
    "         markersize=10, \n",
    "         label='cluster centroid'\n",
    "        )    \n",
    "ax3.set_title('labeled clusters (kmeans model)')\n",
    "ax3.legend(loc='best')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, so what do we have in the plots above?\n",
    "\n",
    "\n",
    "- Left: this is all of the data we generated, but without regard to the ground truth labels\n",
    "- Middle: same data, but now colored and labeled by the ground truth labels \n",
    "- Right: same data, but now we've used a ``KMeans`` model to fit the data. Here, we use most of the default settings, and we specifically told the model that $k=3$.\n",
    "\n",
    "\n",
    "## Duh. Anyone could choose $k=3$ there.\n",
    "\n",
    "Ok, yes, that's true. But let's think about why we \"know\" the answer in this case.\n",
    "\n",
    "My hypothesis (at least, how I think about it) is that in 2-D (and possibly 3-D), my intuition is very reminiscent of the separating planes we discussed in the soft-margin, linear support vector machine algorithm. Recall [that RST session lives in this repository, as well.](https://github.com/DrSkippy/Data-Science-45min-Intros/tree/master/support-vector-machines-101) By maximizing the gap between the separating plane and the data, we identify a cluster that \"feels right.\"\n",
    "\n",
    "That's fine, but what if the data is more complicated? Further, what if we can't even look at the data because it exists in 100-dimensional space?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# even in 3D this gets tough\n",
    "#\n",
    "# use cntl-return to run this a few times - it's fun to see the variations\n",
    "%run 3d-example.py --samples 500 --clusters 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After a few runs of the figure above, we see that sometimes we can clearly make out the clusters. While we *might* be able to manually label these at times, the truth is we don't want to have to look at the data and use our intuition - even if it is \"experienced.\" We want to use one (or more) quantitative metric to inform a decision about a \"good\" choice for $k$. This will certainly scale better than our judgement. \n",
    "\n",
    "\n",
    "\n",
    "# How to choose $k$\\*\n",
    "\n",
    "\n",
    "\\*more accurately: \"what techniques have other people come up with to determine methods for calculating $k$?\"\n",
    "\n",
    "This is not a new problem, though there appear to still be new techniques to solve it. Here are the ones we'll go over in this session:\n",
    "\n",
    "- The Rule of 👎\n",
    "- The Elbow Method \n",
    "- The Gap Statistic \n",
    "\n",
    "There are more, and I've added some references at the end for additional places you could go from here.\n",
    "\n",
    "\n",
    "\n",
    "## The Rule of Thumb\n",
    "\n",
    "This one is kind of awful. I'm only including it because it's always good to be skeptical of easy answers. [According to Wikipedia](https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set#cite_note-1), this comes from: Kanti Mardia et al. (1979). Multivariate Analysis. Academic Press.\n",
    "\n",
    "I didn't look up the original source, but the formula given is:\n",
    "\n",
    "$k \\approx \\sqrt{\\frac{N}{2}} $\n",
    "\n",
    "If we return to the data generation choices from above..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"\"\"With the selection of {} samples (which we know belong to {} clusters), \n",
    "the rule of thumb would suggest there are:\n",
    "\n",
    "\n",
    "{} clusters\n",
    "\n",
    "\n",
    "¯\\_(ツ)_/¯\n",
    "\"\"\".format(samples, clusters, int(math.sqrt(samples / 2))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, so that's a simple heuristic, but it's not well motivated, and not very satisfying. Don't use that one. \n",
    "\n",
    "\n",
    "\n",
    "## The Elbow Method\n",
    "\n",
    "\n",
    "The \"elbow method\" is an approach that makes use of some **single-valued metric that is calculated once the model has converged**. A plot of this metric ideally demonstrates an \"elbow\" as a function of $k$, which represents a diminishing tradeoff between model complexity and added explanatory value. For a quick result, this is probably the most intuitive approach. \n",
    "\n",
    "So, what kind of metric do we use?\n",
    "\n",
    "\n",
    "\n",
    "**`KMeans().intertia_`**\n",
    "\n",
    "One such metric is the single-valued `inertia_` attribute of a fit [`KMeans`](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html#sklearn.cluster.KMeans) instance. Once the  `KMeans` model has converged, we can reach into the `KMeans` object and grab this value. It is calculated by summing (over each cluster, $k$) the squared distance\\* of each sample $x_i$ from its assigned cluster centroid $c_k$:\n",
    "\n",
    "$$ \\text{inertia} = \\sum_{clusters,k} \\sum_{points,i} || \\vec x_{k,i} - \\vec c_k ||^2 $$\n",
    "\n",
    "In this way, the `inertia` is a metric of *intra-cluster variance* (which you would then work to optimally minimize). \n",
    "\n",
    "There are a couple of things to keep in mind: it doesn't include any notion of cluster separation, and in the extreme case of $k=N$ clusters, the inertia goes to zero. So we can already see that we can't just optimize for an extrema in this metric.\n",
    "\n",
    "This metric (or a variation on it) also seems to often be refered to as the SSQ (sum of squared deviations).\n",
    "\n",
    "Below, we'll define a couple of functions to look at this quantity. The first function will take a set of data and range of $k$s to fit over, and return an array of the resulting inertia metrics. For now, only worry about the ``else:`` clause in the ``for`` loop. \n",
    "\n",
    "The second method will provide us a plot of this data so we can look for the elbow.\n",
    "\n",
    "----\n",
    "\n",
    "\\*the `scikit` docs say \"sum of distances\", but if you [source dive](https://github.com/scikit-learn/scikit-learn/blob/bb39b49/sklearn/cluster/k_means_.py#L479) far enough, I think you find it is actually the sum of squared distances."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Modified from (c) 2014 Reid Johnson (BSD License)\n",
    "# http://www3.nd.edu/~rjohns15/cse40647.sp14/www/home.php\n",
    "    \n",
    "def calculate_ssq(data, ks=range(1,11), variance_norm=True):\n",
    "    \"\"\"\n",
    "    Calculate the sum of squared deviations for a range of k with a given set of data.\n",
    "    \n",
    "    Args:\n",
    "      data ((n,m) NumPy array): The dataset on which to compute the gap statistics.\n",
    "      ks (list, optional): The list of values k for which to compute the gap statistics. \n",
    "        Defaults to range(1,11), which creates a list of values from 1 to 10.\n",
    "      variance_norm (boolean, optional): normalize the sum of squared deviations to \n",
    "        a percentage of variance explained. Defaults to True (normalized).\n",
    "\n",
    "    Returns:\n",
    "      ssqs: an array of SSQs, one computed for each k.\n",
    "    \"\"\"\n",
    "    # array for SSQs \n",
    "    ssqs = np.zeros(len(ks)) \n",
    "\n",
    "    # iterate over the range of k values        \n",
    "    for (i,k) in enumerate(ks): \n",
    "        # fit a KMeans model on the data\n",
    "        km = KMeans(n_clusters=k, n_init=2, n_jobs=-1).fit(data)\n",
    "        \n",
    "        if variance_norm:\n",
    "            # normalize to percentage of variance\n",
    "            #\n",
    "            # get the distances from ecah point to the closest centroid\n",
    "            dist = np.min(\n",
    "                        # calc the euclidean dist b/w each point and all clusters\n",
    "                        distance.cdist(data, km.cluster_centers_,'euclidean')\n",
    "                        , axis=1)\n",
    "            # total within-cluster sum of squared distances\n",
    "            tot_withinss = sum(dist**2) \n",
    "            # The total sum of squares\n",
    "            totss = sum(\n",
    "                        # pairwise euclidean distances b/w all points\n",
    "                        distance.pdist(data, metric='euclidean')**2\n",
    "                        ) / data.shape[0] \n",
    "\n",
    "            # The between-cluster sum of squares\n",
    "            betweenss = totss - tot_withinss \n",
    "            ssqs[i] = betweenss/totss*100\n",
    "        else:\n",
    "            # use the built-in inertia metric \n",
    "            # (the sum of squared distances between data and assigned centroids)\n",
    "            ssqs[i] = km.inertia_\n",
    "    return ssqs\n",
    "\n",
    "def plot_ssq_statistics(ssqs, variance_norm=True):\n",
    "    \"\"\"\n",
    "    Generates and shows plots for the sum of squares (SSQ).\n",
    "\n",
    "    A figure with one plot is generated. The plot is a bar plot of the \n",
    "    SSQ computed for each value of k.\n",
    "\n",
    "    Args:\n",
    "      ssqs (NumPy array): An array of SSQs, one computed for each k.\n",
    "      variance_norm (boolean, optional): a hack to get the y-axis label \n",
    "        to reflect the normalization. Defaults to True (normalized).\n",
    "    \"\"\"\n",
    "    # size this one a bit more narrow just for aesthetics below\n",
    "    fig = plt.figure(figsize=(7.5,4))\n",
    "\n",
    "    ind = range(1,len(ssqs)+1) # the x values for the ssqs\n",
    "    plt.plot(ind, ssqs)\n",
    "\n",
    "    plt.ylim(0, max(ssqs)*1.2)\n",
    "    plt.xlim(0, len(ssqs)+1.0)  \n",
    "    \n",
    "    #plt.title('Clustering SSQ', fontsize=14)\n",
    "    plt.xlabel('Number of clusters k', fontsize=14)\n",
    "    # hack to get the right labels depending on how we calculated the SSQ\n",
    "    if variance_norm:\n",
    "        plt.ylabel('Percentage of variance explained', fontsize=14)\n",
    "    else:\n",
    "        plt.ylabel('SSQ (KMeans inertia)', fontsize=14)\n",
    "    plt.xticks(ind)\n",
    "    \n",
    "# switch back to original theme\n",
    "sns.set(style='darkgrid', palette='deep')    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's choose some example parameters and use these functions on the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set some parameters\n",
    "clusters = 4\n",
    "samples = 100\n",
    "\n",
    "\n",
    "# generate new data\n",
    "X, y = make_blobs(n_samples=samples, \n",
    "                  centers=clusters, \n",
    "                  n_features=2, \n",
    "                  cluster_std=1.0, \n",
    "                  # fix random_state if you believe in determinism\n",
    "                  #random_state=42\n",
    "                 )\n",
    "\n",
    "# show the clusters as created \n",
    "f, ax = plt.subplots(1,1, figsize=(8,4))\n",
    "for i in range(clusters):\n",
    "    ax.plot(X[y==i,0], X[y==i,1], 'o', label='cluster {}'.format(i))\n",
    "ax.set_title('labeled clusters (ground truth)')\n",
    "ax.legend(loc='best')\n",
    "\n",
    "# calculate ssq for each value of k\n",
    "ssqs = calculate_ssq(X, ks=range(1,11), variance_norm=False)\n",
    "# plot them\n",
    "plot_ssq_statistics(ssqs, variance_norm=False) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depending on how your `make_blobs()` came out, you might want to use control-enter a few times to get an interesting set of points. \n",
    "\n",
    "Note that based on the formula, **as the number of samples (data points) goes up, so does the inertia metric.** This can make it hard to compare e.g. different sampling choices from a large dataset. In this case, there are at least two obvious paths that make it easier to compare measurements of inertia across data sets: we can normalize the total inertia by the number of data points. Or, we can alternatively normalize the same distances used in that calculation to represent a percentage of variance explained. \n",
    "\n",
    "** Percentage of variance explained **\n",
    "\n",
    "This approach uses the location of the fit centroids and the input data (not, explicitly, the ``inertia`` value). This value is calculated as a ratio of between-group variance to within-group variance in the data. As I understand it, this is also known as an [F-test](https://en.wikipedia.org/wiki/F-test).\n",
    "\n",
    "In our function defined above, we can switch to using this normalization of percentage of variance observed with the `variance_norm=True` kwarg. This is the code in the ``if:`` block of the ``for`` loop. \n",
    "\n",
    "Here's the same data shown above, but using this version of the metric. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate ssq for each value of k\n",
    "ssqs = calculate_ssq(X, ks=range(1,11), variance_norm=True)\n",
    "# plot them\n",
    "plot_ssq_statistics(ssqs, variance_norm=True) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Now we have a representation of all our original data in terms how the `KMeans` algorithm converged across a portion of $k$ parameter space. It's certainly better than eye-balling the $N$ data points in order to select $k$. But - as you've probably realized by now - we **still have to apply our own judgement at this point** to identify the \"elbow\". How much explained variance is \"enough\"?\n",
    "\n",
    "There seems to be a bit of literature on how to use this output as input to another algorithm,  but ultimately someone somewhere has to draw a line in the sand and *declare a parameter.* Say, \"80% variance explained,\" or \"an threshold of 10% or more variance explained added per step.\" \n",
    "\n",
    "So, this method can work. It reduces a massive parameters space and total lack of quantitative metrics into a small (possibly one-dimensional) space, where you can at least make an informed (and data-driven) decision about your choice of $k$. For example, since the average complexity of the kmeans algorithm is $O \\left( k \\cdot N \\cdot T \\right)$ - where $T$ is the number of model iterations per step - you may want to choose $k$ based mainly on evaluation complexity.\n",
    "\n",
    "\n",
    "We can also take this concept one step further with the \"gap statistic\".\n",
    "\n",
    "\n",
    "## The Gap Statistic\n",
    "\n",
    "The gap statistic is an attempt to intelligently choose something like the elbow point above. It is defined in \"Estimating the number of clusters in a data set via the gap statistic\" (Tibshirani, Walther, Hastie, J. R. Statist. Soc. B (2001) 63, Part 2, pp 411-423). From the paper summary: \n",
    "\n",
    "> [the technique compares] the change in within-cluster dispersion with that expected under an appropriate reference null distribution... a simulation shows that the gap statistic usually outperforms other methods that have been propsed in the literature.\n",
    "\n",
    "What this means is that for each value of $k$, we'll fit a `KMeans` model with $k$ clusters to the real data, and then also **fit an identical `KMeans` model to a bunch of null distribution models e.g. randomly-distributed data** in the same parameter space. For each value of $k$, calculate the within cluster dispersion (similar to how we did this above) for both the real data the reference distributions. **The gap statistic $\\text{gap}_k$ is a function of these two metrics** (approximately the mean of the point-by-point differences in the logarithms, see ~line 117 in `gap.py`). From fitting the reference (null) distributions, there will be a distribution of variation in this dispersion from which we calculate the standard deviation (or standard error), $\\text{err}_k$. \n",
    "\n",
    "**The optimal number of clusters is then the smallest $k$ for which \n",
    "$\\text{gap}_k \\ge \\text{gap}_{k+1} - \\text{err}_{k+1}$.**\n",
    "\n",
    "Let's apply this to the same data we had before. It looked like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# show the clusters as created \n",
    "f, ax = plt.subplots(1,1, figsize=(8,4))\n",
    "for i in range(clusters):\n",
    "    ax.plot(X[y==i,0], X[y==i,1], 'o', label='cluster {}'.format(i))\n",
    "ax.set_title('labeled clusters (ground truth)')\n",
    "ax.legend(loc='best')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, to see this in action we define two functions - similar to the SSQ-related functions above: one to calculate the new metric, and one to plot the output. \n",
    "\n",
    "Since the code is bit long, it is contained in the separate module ``gap.py``. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from gap_stats import gap_statistics\n",
    "from gap_stats import plot_gap_statistics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# for the range of given ks, calculate the gaps, errors, and differences\n",
    "# (this one can take a minute)\n",
    "gaps, errs, difs = gap_statistics(X, ks=range(1,11))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# then show them\n",
    "plot_gap_statistics(gaps, errs, difs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** If you get a result of $k=1$ and that looks - by eye - to be very incorrect, run it again with new data... more on this below.\n",
    "\n",
    "\n",
    "To see the gap statistic in action on a bigger scale, we can return to the 3D example from earlier and (hopefully) observe that this is a better choice than \"eyeballing it.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# this one may take a minute. it has to fit (clusters * (10+1) * 2) kmeans models\n",
    "#    each with O( k * n * 2 ) complexity\n",
    "\n",
    "%run 3d-example.py --samples 200 --clusters 7 --gap True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Final thoughts\n",
    "\n",
    "In experimenting with this formulation, one place that I've seen the gap statistic come up short in it's prediction of \"best $k$\" is when the gap difference is a slightly $\\gt 0$ at $k=1$, but then negative until a large (and potentially \"correct\", from the ground truth) value of $k$. I haven't come across a way to work with this yet... perhaps a follow-up RST topic.\n",
    "\n",
    "As with many algorithmic approaches to data, there seem to be many ways to tackle this problem and more constantly being developed. Some of the techniques that I came across while preparing this RST but didn't have time to pursue include:\n",
    "\n",
    "- information criteria techniques (which you can see examples of in the [\"model selection\" RST](https://github.com/DrSkippy/Data-Science-45min-Intros/tree/master/model-selection-101))\n",
    "- use of the [\"silhouette coefficient\"](http://scikit-learn.org/stable/modules/clustering.html#silhouette-coefficient)\n",
    "- [Dirichlet process mixture models](https://en.wikipedia.org/wiki/Dirichlet_process#Use_in_Dirichlet_mixture_models)\n",
    "\n",
    "... and there are likely many more, as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
